package com.dmall.play.interview.chapter07;

import sun.reflect.generics.tree.Tree;

public class Leetcode101V1 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    }

    public boolean isSymmetric(TreeNode root) {
        TreeNode copyRoot = copyRoot(root);
        TreeNode newRoot = invertTree(root);
        return isSameTree(copyRoot, newRoot);
    }

    private TreeNode copyRoot(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode copyLeft = copyRoot(root.left);
        TreeNode copyRight = copyRoot(root.right);
        TreeNode copyRoot = new TreeNode(root.val);
        copyRoot.left = copyLeft;
        copyRoot.right = copyRight;
        return copyRoot;
    }

    private TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

    private boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null) {
            return false;
        } else if (q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            // else 表示 p 和 q 的 val 相等
            boolean sameLeft = isSameTree(p.left, q.left);
            boolean sameRight = isSameTree(p.right, q.right);
            return sameLeft && sameRight;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(3);

        Leetcode101V1 leetcode101V1 = new Leetcode101V1();

        TreeNode copyRoot = leetcode101V1.copyRoot(root);
        System.out.println(copyRoot);

        //System.out.println(leetcode101V1.isSymmetric(root));
    }
}
